import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/5 9:56
 * @description 单调栈，栈内保存最大元素的下标
 */
public class Solution3 {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        ListNode listNode = new ListNode(2, new ListNode(7, new ListNode(4, new ListNode(3, new ListNode(5)))));
        solution3.nextLargerNodes(listNode);
    }
    public int[] nextLargerNodes(ListNode head) {
        int[] nums = new int[10001];
        int len = 0;
        // 一次遍历，将值保存下来
        while (head != null) {
            nums[len++] = head.val;
            head = head.next;
        }

        int[] ret = new int[len];
        int[] descStack = new int[len];
        int topIdx = -1;
        for (int i = 0; i < len; i++) {
            while (topIdx != -1 && nums[descStack[topIdx]] < nums[i]) {
                ret[descStack[topIdx--]] = nums[i];
            }
            // 保存的是当前遍历的最大值的下标，
            descStack[++topIdx] = i;
        }

        while (topIdx != -1) {
            ret[descStack[topIdx--]] = 0;
        }
        return ret;
    }
}
